home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / PASCAL / MISC_ROU / RANDOM.PAS < prev    next >
Pascal/Delphi Source File  |  1991-02-23  |  4KB  |  122 lines
  1. UNIT RandomNumbers;
  2.  
  3. {  This unit implements a "minimal standard" random number generator
  4.    whose parameters are optimal for 32-bit arithmetic.  This is not the
  5.    "best" random number generator possible, but it is simple, quick,
  6.    and produces numbers which are "random" enough for most purposes.
  7.  
  8.    It is based on the "parametric multiplicative linear congruential
  9.    algorithm" which was originally proposed by D. H. Lehmer in 1951.
  10.    This algorithm generates a sequence of integers z[1], z[2], z[3]...
  11.    by repeatedly carrying out the following calculation:
  12.  
  13.                 z[n+1] = (a * z[n]) mod m
  14.  
  15.    where "a" and "m" are suitable constants.  The successive "z"s are
  16.    stored in the variable "seed" in this unit.  They all lie in the
  17.    range [0..m-1], so dividing them by "m" gives real numbers which
  18.    lie in the range [0..1].
  19.  
  20.    In 1969, Lewis, Goodman and Miller proposed the choice of a = 16807
  21.    and m = 2**31 - 1 = 2147483647 as particularly suited for a machine
  22.    with a 32-bit word length (in their case, the IBM System/360).
  23.    The main problem is that a * z[n] can be more than 32 bits long,
  24.    leading to integer overflow on many systems (including the Mac).
  25.  
  26.    In 1979, G. L. Schrage devised an implementation of the LG&M method
  27.    which is guaranteed not to produce integer overflow on any system
  28.    with a 32-bit word length.  It is this implementation which is 
  29.    used here, in function "RandomReal".
  30.  
  31.    Source:  Stephen K. Park and Keith W. Miller, "Random Number 
  32.    Generators:  Good Ones Are Hard to Find", Communications of the ACM,
  33.    vol. 31, p. 1192  (October 1988).
  34.    
  35.    This unit was written in MPW Pascal, v3.1.
  36.  
  37.    Submitted by:           Jon Bell
  38.                  Dept. of Physics & Comp. Sci.
  39.                      Presbyterian College
  40.                        Clinton SC 29325
  41.                         CIS #70441,353                                 }
  42.  
  43. INTERFACE
  44.  
  45. procedure InitRandomSeed (newSeed : longint);
  46.  
  47. {  Initializes the random number seed to "newSeed".  You must call this
  48.    procedure once, at the beginning of your program, before you use 
  49.    either of the following functions.  As far as randomness is concerned,
  50.    it makes no difference what value you use for "newSeed", so long
  51.    as it isn't zero.  Using different seeds merely gives you different
  52.    sequences of "random" numbers.  Using the same seed each time you
  53.    run the program gives you the same sequence of "random" numbers
  54.    each time, which may be useful for debugging. }
  55.  
  56. function RandomReal : real;
  57.  
  58. {  Returns a real number, "randomly" selected from the interval [0,1].  }
  59.  
  60. function RandomInteger (max : integer) : integer;
  61.  
  62. {  Returns an integer, "randomly" selected from the interval [1,max].   }
  63.  
  64. {-----------------------------------------------------------------------}
  65. {-----------------------------------------------------------------------}
  66.  
  67. IMPLEMENTATION
  68.  
  69. var
  70. seed : longint;
  71.  
  72. {-----------------------------------------------------------------------}
  73.  
  74. procedure InitRandomSeed (newSeed : longint);
  75.  
  76. begin
  77. seed := newSeed
  78. end;
  79.  
  80. {-----------------------------------------------------------------------}
  81.  
  82. function RandomReal : real;
  83.  
  84. const
  85. a = 16807;
  86. m = 2147483647;
  87. q = 127773;
  88. r = 2836;
  89.  
  90. var
  91. lo, hi, test : longint;
  92.  
  93. begin
  94. hi := seed div q;
  95. lo := seed mod q;
  96. test := a * lo - r * hi;
  97. if test > 0 then
  98.     seed := test
  99. else
  100.     seed := test + m;
  101. RandomReal := seed / m
  102. end;
  103.  
  104. {-----------------------------------------------------------------------}
  105.  
  106. function RandomInteger (max : integer) : integer;
  107.  
  108. var
  109. result : integer;
  110.  
  111. begin
  112. result := trunc (RandomReal * max) + 1;
  113. if result > max then
  114.     RandomInteger := max      { This doesn't happen very often. }
  115. else
  116.     RandomInteger := result
  117. end;
  118.  
  119. {-----------------------------------------------------------------------}
  120.  
  121. END.
  122.